In general the invention relates to the surveillance of the reliability of a stream of information bits with the aid of convolutional codes. The standard work in the field is the book by W. W. Peterson et al., "Error correcting codes", MIT, Boston, Mass., 2nd edition 1971, for example page 393. More particularly the invention relates to a system in which an (n, k, p) linear convolutional code is used. Random errors and also in particular circumstances accumulations of errors (bursts) can be corrected with this system.
In an encoding apparatus operating according to this code the incoming stream of information bits is divided into a sequence of groups of k bits, the so-called k-tuples x(j), x(j+1), x(j+2), . . . . Simple examples are k=1 and k=2. From the stream of k-tuples of information elements a sequence corresponding thereto of n-tuples of code elements y(j), j(j+1), y(j+2) . . . is then formed, where n is always greater than k. For n=2 and k=1 the efficiency or "rate" of the code is 1/2, for n=3 and k=2 the efficiency is 2/3. The preferred versions to be described hereinafter give n-k=2. An example of a convolutional code having (n-k)=2 has been described in the Netherlands Patent Application No. 7804673 U.S. Ser. No. 33,718, filed Apr. 27, 1979, now abandoned, but continued as U.S. Ser. No. 257,061, filed Apr. 24, 1981, to the same assignee which has been incorporated herein by reference. Moreover in general an n-tuple of code elements is formed on the basis of more than one k-tuple of information elements. A convolutional code is said to be systematic if the information bits of the k-tuples form unchanged part of the code bits of the n-tuples; in that case the coding process comprises nothing more than the addition of a sequence of (n-k)-tuples composed of parity bits. The invention is not however confined to the use of such systematic convolutional codes. The parameter p is the encoding constraint length. The value of the parameter p is defined in such a way that for the formation of one (n-k)-tuple of parity bits a sequence of (p+1) successive k-tuples of information bits is necessary, in the case of a systematic code. In the case of a non-systematic code these (p+1) successive k-tuples of information bits are necessary for the formation of one n-tuple of code elements. In a corresponding manner a decoding constraint length u (u.gtoreq.p) has been defined: a sequence of (u+1) successive (n-k)-tuples of parity bits, or n-tuples of code bits respectively, is necessary and sufficient for the reconstruction of one k-tuple of information elements. A subsidiary condition that applies here is the placing of a constraint on the permissible number of errors in a running segment of (u+1) successive n-tuples of code elements, in such a way that this reconstruction is possible.
In particular the invention relates to an apparatus for the reception of a stream of binary code elements which form a sequence of n-tuples of an (n,k,p) error-correcting convolutional code, where k/n is the ratio of the number of information elements to the number of code elements corresponding thereto and p is the encoding constraint length, which apparatus includes:
a. first syndrome-forming circuit for forming together with the reception of said sequence of n-tuples of code elements a sequence therefrom composed of (n-k) tuples of binary syndrome elements;
b. a logical unit having first storage means for receiving said (n-k)-tuples of syndrome elements and for storing them temporarily during a time which corresponds to at least (u) bit cells, where u (u.gtoreq.p) is the decoding constraint length of said error-correcting convolutional code, and for forming, always together with the reception of an n-tuple of code elements of said sequence, from a predetermined running selection of said sequence of (n-k)-tuples of syndrome elements, an element of a sequence composed of j-tuples of binary correction elements at a first output of the logic unit, where for a systematic convolutional code j=k and for a non-systematic convolutional code j=n;
c. a correction apparatus for storing at least the information containing part of the sequence of n-tuples of code elements during a time which corresponds to at least (u) bit cells and for thereafter adding this modulo 2 to the corresponding j-tuple of correction elements;
d. a feedback connection for supplying said sequence of j-tuples of correction elements to said logic unit for the updating of the (n-k)-tuples of syndrome elements stored there so as to compensate these for the effects of the correction executed on said sequence of n-tuples of code elements.
Such an apparatus is known from the U.S. Pat. No. 3,697,947. The quantity of errors correctable in a segment of (u+1) n-tuples received is limited and dependent on the chosen values for n, k and p and on the value of u also determined thereby. More errors than this cannot be corrected correctly. If the number of errors in a segment is too large for a correct correction, there are two possibilities for the operation of the correcting algorithm: the correction can be erroneously omitted, or an incorrect correction is applied. In both cases there is a decoding error.